1. Field of the Invention
The present invention generally relates to display rendering. More particularly, the invention relates to systems and methods for graph rendering.
2. Description of Related Art
As the amount and complexity of data increases, there is a need to better explain the data content and as well as potential relationships suggested by the data. One way in which massive data may be described is through the use of graphs. A graph is any visual representation of information or of relationships between quantities, qualities, or sets of data.
A popular graph used to depict data is the force-directed layout graph. The force-based or force-directed graph utilizes force-directed algorithms for drawing graphs in an aesthetically pleasing way. One of the goals for the force-directed algorithm is to lay out the graph in a manner that is comprehensible to the user so that the user can identify components as well as at least some information regarding relationships in the data. In a force-directed layout, the graph generally positions nodes in two-dimensional or three-dimensional space so that all or most of the edges are of equal length and there are as few crossing edges as possible. Forces may be assigned among the sets of edges and the set of nodes. In one example, the forces assigned to the edges act as springs. In other examples, the nodes may act as electrically charged particles.
Unfortunately, as the amount and the number of dimensions of the data grow, the layout of the graph becomes increasingly complex, slow, and computationally expensive. A bad layout may take a long time to draw and may hide or obscure information or relationships thereby rendering the graph ineffective.
Further, existing systems do not scale. The number of computations in existing systems increases dramatically as the number of nodes increases. For example, the number of computations may be N*N for every N number of nodes. As a result, as the amount of data that must be graphed increases, the graphical layout process may slow to the point that the process is no longer useable. Further, existing systems tend to render obscure, non-optimal layouts as the amount of data and/or dimensions increase.
Once a graph layout is determined (e.g., the positions of nodes and edges has been calculated), the graph is displayed. In the prior art, individual, imperative commands are made to construct graphs. For example, a graph may be depicted as a combination of nodes, which may be displayed as balls, and edges, which may be displayed as lines between the balls. In the prior art, separate commands are generated to draw each edge and each node. Further, separate commands are required to color each of the nodes. As a result, as the number of nodes and edges of the graph increase, the number of required commands to draw and color the graph also increases linearly. Once the number of nodes and edges becomes too high, the process of drawing the graph slows and useable performance may be lost. Consequently, many graphs that represent large amounts of data of sufficient complexity require powerful hardware (e.g., computers with state of the art graphic card(s), cutting edge processor(s) with multiple cores, and considerable memory). If the graph is too complex, the graph may not be able to be rendered at all within a reasonable time.
FIGS. 12a-12b depict a process of rendering a graph consisting of nodes coupled by edges to form a ring in the prior art. FIG. 12a depicts a graph 1200 wherein edges 1208-1216 are individually drawn in the prior art. A separate command is generated and sent to a graphic card for each edge. In this example, a command is generated to draw edge 1208. The command is then provided to the graphic card which may then draw the edge. Subsequently, the process continues by generating and providing separate commands for individual edges 1210, 1212, 1214, and 1216, respectively. After generation, each command is separately provided to the graphic card. Upon receiving each command, the graphic card will perform the individual command. FIG. 12a depicts an incomplete graph where additional individual commands to draw each unfinished edge, respectively, will be required.
FIG. 12b depicts a graph 1202 wherein edges have been completed and nodes 1218-1224 are individually drawn in the prior art. In the prior art, each node is individually drawn as a mesh (e.g., a polygon mesh). As a result, each node 1218-1224 is individually drawn by separate commands. For example, a command is generated to draw node 1218. The command is then sent to the graphic card. Subsequently, separate commands are generated to draw each node 1220, 1222, and 1224, respectfully. After generation, each command is separately provided to the graphic card. FIG. 12b depicts an incomplete graph where additional individual commands to draw each unfinished node, respectively, will be required.
FIG. 12c depicts a graph 1204 wherein edges and nodes have been completed and nodes 1226-1232 are individually colored in the prior art. For example, node 1226 may be colored once a command to fill the mesh (e.g., fill faces of the polygons associated with the drawing of node 1226) is generated and provided to the graphic card. Separate commands are required to color each individual node 1226-1232. Upon receiving each command, the graphic card may fill each node in turn. FIG. 12c depicts an incomplete graph where additional individual commands to fill each unfinished node, respectively, will be required.
FIG. 12d depicts a finished graph 1206 after separate commands have been generated for each component of the graph 1206 in the prior art. Graph 1206 depicts a circular graph consisting of colored nodes and connecting edges. Those skilled in the art will appreciate that the shape, number of nodes, and complexity of the graph 1206 are fairly trivial. As the number and position of nodes and edges increase, however, the number of individual commands and individual actions necessary to draw the graph dramatically increase. As a result, performance may slow to the point where displaying the graph cannot be performed in a reasonable time.
Further, as the complexity of the graph grows, inconsistent changes or details that may otherwise be included in the graph are not longer practical. For example, changes in size and different colors of the nodes may require additional resources which may not be available.